package com.shiguiwu.springmybatis.algorithm.sort;

import java.util.Arrays;

/**
 * @description: 基数排序
 * 空间换时间
 * @author: stone
 * @date: Created by 2021/3/27 12:46
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.sort
 */
public class RadixSort extends AbstractSort implements Sort {

    public static void main1(String[] args) {
        test2();
    }
    public RadixSort(int[] array) {
        super(array);
    }

    @Override
    public void sort() {
        //初始化一个桶
        int[][] bucket = new int[10][array.length];
        //初始化记录桶内数组的个数
        int[] counts = new int[10];
        int max = 0;
        for (int value : array) {
            if (value > max) {
                max = value;
            }
        }

        String str = String.valueOf(max);
        int len = str.length();
        //取出数组来
        for (int j = 0,n = 1; j < len; j++,n*=10) {
//            int n = (int) Math.pow(10, j);
            for (int value : array) {
                int t = (value / n) % 10;
                bucket[t][counts[t]] = value;
                counts[t]++;
            }

//            System.out.println("第 "+j +"次排序。。。。。。。"+Arrays.toString(counts));

            int index = 0;
            //放回原数组中。。。。。。。
            for (int i = 0; i < counts.length; i++) {
                int c = 0;
                while (counts[i]>0 && c < counts[i]) {
                    array[index] = bucket[i][c];
                    index++;
                    c++;
                }
                //每次取出数据之后记得清空数据，以便于下次使用
                counts[i] = 0;
            }
//            System.out.println(Arrays.toString(array));
        }

    }

    public static void test2() {

        int[] test = {21, 525,40, 13, 9,32, 82};
        //初始化一个桶
        int[][] bucket = new int[10][test.length];
        //初始化记录桶内数组的个数
        int[] counts = new int[10];
        int max = 0;
        for (int i = 0; i < test.length; i++) {
            if (test[i] > max) {
                max = test[i];
            }
        }

        String str = String.valueOf(max);
        int len = str.length();
        for (int j = 0,n = 1; j < len; j++,n*=10) {
//            int n = (int) Math.pow(10, j);
            for (int i = 0; i < test.length; i++) {
                int t =  (test[i]/n)  % 10;
                bucket[t][counts[t]] = test[i];
                counts[t]++;
            }

            System.out.println("第 "+j +"次排序。。。。。。。"+Arrays.toString(counts));

            int index = 0;
            for (int i = 0; i < counts.length; i++) {
                int c = 0;
                while (counts[i]>0 && c < counts[i]) {
                    test[index] = bucket[i][c];
                    index++;
                    c++;
                }
                //每次取出数据之后记得清空数据
                counts[i] = 0;
            }
            System.out.println(Arrays.toString(test));
        }







    }


    public static void test() {

        int[] test = {21, 5,40, 13, 9,32, 82};
        //初始化一个桶
        int[][] bucket = new int[10][test.length];
        //初始化记录桶内数组的个数
        int[] counts = new int[10];


        //第一次排序
        for (int i = 0; i < test.length; i++) {
            int t =  (test[i]/1)  % 10;
            bucket[t][counts[t]] = test[i];
            counts[t]++;
        }

        System.out.println("第一次排序。。。。。。。"+Arrays.toString(counts));

        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            int c = counts[i];
            while (c!= 0) {
                test[index] = bucket[i][c-1];
                index++;
                c--;
            }
            counts[i] = 0;
        }
        System.out.println(Arrays.toString(test));

        //第二次排序
        for (int i = 0; i < test.length; i++) {
            int t = (test[i]/10) % 10;
            bucket[t][counts[t]] = test[i];
            counts[t]++;
        }

        System.out.println("第二次排序。。。。。。。"+Arrays.toString(counts));

        index = 0;
        for (int i = 0; i < counts.length; i++) {
            int c = 0;
            while (counts[i]>0 && c < counts[i]) {
                test[index] = bucket[i][c];
                index++;
                c++;
            }
            counts[i] = 0;
        }
        System.out.println(Arrays.toString(test));


    }
}
